In many large scale integration (LSI) circuits and central processing units (CPUs), high-speed operation of circuits is achieved by pipeline processing. Note that in pipeline processing, a circuit is divided into a plurality of processing units connected in series and the plurality of processing units concurrently perform processing in accordance with instructions. One of the plurality of processing units outputs an instruction which has been processed to a processing unit in the next stage after the processing, and a new instruction from a processing unit in the previous stage is input to the one of the plurality of processing units. In this manner, the processing units can efficiently operate.
However, in pipeline processing, operation of the plurality of processing units is suspended (also referred to as a pipeline hazard or hazard) in some cases. For example, a hazard can occur in the case where a conditional branch instruction is input to the plurality of processing units. Note that a conditional branch instruction is an instruction by which a branch occurs if a condition is satisfied. In this case, whether or not the branch occurs is not known before an operation of a processing unit (also referred to as an arithmetic portion) that judges whether or not the condition is satisfied. Therefore, until whether or not the branch occurs is known, operation of a processing unit (also referred to as a reading portion) that reads (fetches) an instruction needs to be suspended, which causes delay in circuit operation.
In view of that fact, there is a known technique (branch prediction) in which prediction of whether or not a branch occurs allows a reading portion to keep operating even before whether or not the branch occurs is known (for example, see Patent Document 1). In this manner, the circuit can operate without delay in the case where the prediction is right.